长大后想做什么？做回小孩！

0%

[LeetCode]——最长回文串

发表于 分类于 Valine：
本文字数： 111

NO.409 最长回文串 简单

8rnh8S.png

思路一：哈希表 能组成回文串的字符特点应该是偶数个，只能有一个奇数个的字符作为中心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestPalindrome(String s) {
    if (s==null||s.length()<1)return 0;
    int len = s.length(),maxLen=0;
    HashMap<Character,Integer> map=new HashMap<>();
    //遍历字符串
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        Integer value = map.getOrDefault(c, 0);
        //如果当前字符已经存在一个，可以成对则加入回文子串，并重新计数
        if (value==1){
            maxLen+=2;
            map.put(c,0);
        }else {
            map.put(c,1);
        }
    }
    //如果有未使用的字符，可以任取一个作为中心
    return maxLen==len?maxLen:maxLen+1;
}

时间复杂度：O(n)

可以改用数组代替hashmap：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestPalindrome(String s) {
    if (s==null||s.length()<1)return 0;
    int len = s.length(),maxLen=0;
    int[] map=new int[128];
    //遍历字符串
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        //如果当前字符已经存在一个，可以成对则加入回文子串，并重新计数
        if (map[c]==1){
            maxLen+=2;
            map[c]=0;
        }else {
            map[c]=1;
        }
    }
    //如果有未使用的字符，可以任取一个作为中心
    return maxLen==len?maxLen:maxLen+1;
}

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github